#ifndef SORT_H_
#define SORT_H_

#include <cstddef>
#include <optional>

namespace lxj
{

// 在一个有序数组中找到数字num；
// 当num不存在时，若lr==true，返回数组中<num中最右的数，否则返回>num中最左的数
inline constexpr std::optional<int> searchNum(int num, int* arr, size_t len, bool lr = true)
{
    if (len == 0) return std::nullopt;
    size_t left = 0, right = len;
    int    mid = 0;
    while (left != right) {
        mid = left + (right - left) / 2;
        if (arr[mid] == num) {
            break;
        }
        else if (arr[mid] > num) {
            right = mid;
        }
        else {
            left = mid + 1;
        }
    }
    if (arr[mid] != num) {
        if (lr) {
            mid = arr[mid] < num ? mid : mid - 1;
        }
        else {
            mid = arr[mid] > num ? mid : mid + 1;
        }
    }
    mid = 0 <= mid && mid < len ? mid : (0 > mid ? 0 : len - 1);
    return std::make_optional(mid);
}

/*
    寻找峰值
    在一随机不重复数组中返回任意一个峰值的下标，例如arr{54,99,31}，arr[1]是一个峰值
    设定arr[-1]和arr[len]位置元素为INT_MAX
*/
inline constexpr std::optional<int> peakIndex(int* arr, size_t len)
{
    if (len <= 0) return std::nullopt;
    if (len == 1) return std::make_optional(0);
    if (arr[0] > arr[1]) return std::make_optional(0);
    if (arr[len - 1] > arr[len - 2]) return std::make_optional(len - 1);

    size_t l = 1, r = len - 1, mid = 0;
    while (l < r) {
        mid = l + (r - l) / 2;
        if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
            break;
        }
        else if (arr[mid] < arr[mid + 1]) {
            l = mid;
        }
        else {
            r = mid - 1;
        }
    }
    return std::make_optional(mid);
}

}   // namespace lxj

#endif